//
// Created by ct on 2021/10/27.
//

#include <vector>
#include <iostream>
#include <unordered_set>
#include <queue>
using std::priority_queue;
using std::cout;
using std::endl;
using std::unordered_set;

#include "linked_list.h"

bool SolutionLinkedList::hasCycle(ListNode *head) {
    if (head == nullptr) {
        return false;
    }
    ListNode *fast = head, *slow = head;
    if (fast->next == nullptr) {
        return false;
    }
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        if (fast == slow) {
            return true;
        }
        slow = slow->next;
    }
    return false;
}
listNode *SolutionLinkedList::create_linked_list(vector<int> &nums) {
    auto *root = new ListNode(nums[0]);
    auto *curr = root;
    int len = (int) nums.size();
    for (int i = 1; i < len; ++i) {
        auto *t = new ListNode(nums[i]);
        curr->next = t;
        curr = curr->next;
    }
    return root;
}
void SolutionLinkedList::printLinkedList(ListNode *head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}
bool SolutionLinkedList::hasCycleSet(ListNode *head) {
    unordered_set<ListNode *> seen;
    while (head != nullptr) {
        if (seen.count(head)) {
            return true;
        }
        seen.insert(head);
        head = head->next;
    }
    return false;
}
ListNode *SolutionLinkedList::mergeKLists(vector<ListNode *> &lists) {

     struct Status {
        int val;
        ListNode * ptr;
         bool operator < (const Status &rhs) const {
             return val > rhs.val;
         }
    };
     // 优先队列
    priority_queue<Status> q;

    for (auto listNode : lists) {
        q.push({listNode->val,listNode});
    }
    ListNode head(-1);
    ListNode * tail = &head;
    while (!q.empty()) {
        auto f = q.top(); q.pop();
        tail->next = f.ptr;
        tail = tail->next;
        if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
    }
    return head.next;
}
ListNode *SolutionLinkedList::mergeTwoLists(ListNode *l1, ListNode *l2) {
    if ((l1 == nullptr) || (l2 == nullptr)) return l1 != nullptr ? l1 : l2;
    ListNode head(-1), *tail = &head;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            // 连接l1,l1滑动
            tail->next = l1;
            l1 = l1->next;
        } else {
            // 连接l2,l2滑动
            tail->next = l2;
            l2 = l2->next;
        }
        // tail滑动
        tail = tail->next;
    }
    tail->next = l1 != nullptr ? l1 : l2;
    return head.next;
}


void print(){
    std::cout << " hello "<<std::endl;
}



/*    if ((!a) || (!b)) return a ? a : b;
    ListNode head(-1), *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr != nullptr && bPtr != nullptr ){
        if(aPtr->val < bPtr->val){
            tail->next = aPtr;
            aPtr = aPtr->next;
        } else {
            tail->next = bPtr;
            bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next =  (aPtr ? aPtr : bPtr);
    return head.next;*/